typedef int KeyType ; /* 整型 */


typedef struct RecType
{
    KeyType key ; /* 关键字码 */
}RecType ;

#define EQ(a, b) ((a)==(b))   //equal
#define LT(a, b) ((a)<(b))    //less than
#define LQ(a, b) ((a)<=(b))   //less than or equal
#define MAX_SIZE 100

typedef struct SSTable {
    RecType elem[MAX_SIZE]; /* 顺序表 */

    int length; /* 实际元素个数 */

} SSTable;

int Seq_Search(SSTable ST, KeyType key) {
    int p;

    ST.elem[0].key = key; /* 设置监视哨兵, 失败返回 0 */

    for (p = ST.length; !EQ(ST.elem[p].key, key); p--);
    return (p);

}

int Bin_Search(SSTable ST, KeyType key) {
    int Low = 1, High = ST.length, Mid;
    while (Low < High) {
        Mid = (Low + High) / 2;
        if (EQ(ST.elem[Mid].key, key))
            return (Mid);
        else if (LT(ST.elem[Mid].key, key))
            Low = Mid + 1;
        else High = Mid - 1;
    }
    return (0); /* 查找失败 */
}

typedef struct IndexType {
    keyType maxkey; /* 块中最大的关键字 */
    int startpos; /* 块的起始位置指针 */
} Index;

/* 在分块索引表中查找关键字为 key 的记录 */
/* 表长为 n ，块数为 b */
int Block_search(RecType ST[], Index ind[], KeyType key, int n, int b)
{
    int i = 0, j, k;
    while ((i < b) && LT(ind[i].maxkey, key)) i++;
    if (i > b) {
        printf("\nNot found");
        return (0);
    }
    j = ind[i].startpos;
    while ((j < n) && LQ(ST[j].key, ind[i].maxkey)) {
        if (EQ(ST[j].key, key)) break;
        j++;
    } /* 在块内查找 */
    if (j > n || !EQ(ST[j].key, key)) {
        j = 0;
        printf("\nNot found");
    }
    return (j);
}




int main()
{
    SSTable ST; //2,4,6,8,10,12,14,16,18
    ST.length = 0;
    int i;
    int position;
    for (i=1; i < 10; i++) {
        ST.elem[i].key = i*2;
        ST.length++;
    }
//    KeyType x;
//    printf("input 5 numbers:\n");
//    for(i=1; i<=5; i++){
//        scanf("%d", &x);
//        ST.elem[i].key = x;
//        ST.length++;
//    }
//    printf("%d", ST.length);
//    for (i=1; i < 10; i++) {
//        printf("%d,", ST.elem[i].key);
//    }
    position = Seq_Search(ST, 101);
    printf("%d", position);
}